1. Field of the Invention
The invention concerns name translation generally and more particularly name translation in communications networks.
2. Description of the Prior Art
As networks have grown more complex, it has become more and more worthwhile to give users of the networks techniques for reaching other users which are not dependent on the actual addressing mechanisms used in the networks. One example of such a technique is the 800 number, described in detail in U.S. Pat. No. 4,191,860, Roy P. Weber, Data Base Communication Call Processing Method, issued Mar. 4, 1980. The 800 number is not itself an actual telephone number, but instead represents an actual telephone number. When a telephone switch receives an 800 number, it sends a message with the 800 number to a network control point which contains a data base relating the 800 number to an actual telephone number. The network control point returns a message to the switch which contains the actual telephone number corresponding to the 800 number, and the switch then uses the actual number to set up the telephone call. The fact that the 800 number is not an actual telephone number provides a high degree of flexibility: the number may be a mnemonic for the business which is using the 800 number, the business may change its actual telephone number without changing its 800 number, the 800 number may correspond to different actual telephone numbers in different parts of the country or at different times of day, and the 800 number may even correspond to more than one actual telephone number, with calls being divided among the actual telephone numbers according to a load balancing scheme.
Calls made using 800 numbers are already an important part of the business of telephone companies. Moreover, the growing need for portability in the telephone system will make numbers which work like the 800 number even more important. For instance, in the future, each person may be given a single lifetime telephone number which may be used to reach him no matter where he is. As more and more of the numbers used in the telephone system are numbers like 800 numbers, it becomes more and more important that the translation of such numbers to the actual numbers be done as quickly and with as little extra network traffic as possible.
The problem of making the user of a network independent of the addressing mechanisms actually employed in the network is of course encountered in any network. The general solution is to establish a correspondence in the network between a name and a network address. In this context, a network address is a value used internally by the network to address a user of the network and a name is another value which is not itself a network address but represents a network address. In the context of the telephone system, an actual telephone number is a network address and an 800 number is a name. Once the correspondence between the network address and the name is established, a user of the system can provide the network with a name and the network can translate the name into its corresponding network address and then use the network address to establish communications between the user and the desired destination.
The component of the network in which the correspondence between a name and a network address is established is termed a name server. The name server maintains a list of names and their corresponding network addresses. When a node of the network sends the name server a message containing a name, the name server looks the name up in the list and returns a message containing the corresponding network address. In the context of the telephone system, the network control point is a name server for 800 numbers.
As with the telephone network, a critical issue in other networks which employ names is the efficiency of name translation, the translation of a name into the network address which it represents. The simplest way to do name translation is in the manner described above for 800 numbers, i.e., the network address is always obtained from the name server; difficulties with this technique include the time it takes to do a translation and the number of messages required to do it. As regards the time, the switch which has received the name must send the name to the name server and wait until the name server has returned the corresponding network address before it can begin communicating. As regards the number of messages, when a name is used instead of a network address, two extra messages must be sent before the switch can begin communicating.
One technique which has been used in the past to speed up translation is name caches in nodes of the network. In general terms, a name cache contains copies of some of the correspondences between names and network addresses from the name server. When a node receives a name, it looks first in the name cache. If the name cache has a copy of the correspondence between the name and the network address, the node uses the network address from the cache to begin communications; otherwise, it goes to the name server as described above. When the node obtains the corresponding address from the name server, it not only begins communications, but also adds the name and the corresponding address to the name cache. As may be seen from the foregoing, once a name is in the cache, the node can begin communicating without exchanging messages with the name server.
A difficulty with name caches is keeping the name-network address correspondences contained in a cache consistent with the name-network correspondences presently in use in the network. For example, as mentioned above, in an 800 number system, the actual telephone number corresponding to an 800 number may vary according to a load-balancing scheme; when the relationship between the 800 number and the actual telephone number changes in the name server, it must also change in all of the name caches in the network. A prior-an solution to the problem has been to periodically invalidate part or all of the name cache (see for example U.S. Pat. No. 4,706,801, Hart, et al., Method and Apparatus for Bridging Local Area Networks, issued Nov. 10, 1987). There, bridges connecting LANs have tables containing source and destination addresses for the stations connected to the LANs. If a bridge does not receive a frame containing one of the values in the table for a period of about 15 minutes, the value is deleted from the table. There are two difficulties with this approach: the first is that an invalid entry may remain in the table for up to fifteen minutes, and may be used by the system during that period. The second is that mere non-use of a source or destination address for a relatively short time may cause the address to be removed from the table. When the source or destination address is again used, it must again be incorporated into the table.
What is needed, and what is provided by the present invention, is a name translation technique which employs name caches, but which avoids the opportunities for error and the excess overhead associated with partial or complete name cache invalidation.